package algorithm.t202110;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/14 8:58
 * @description : 9道
 */
public class t20211014 {

    //344.反转字符串
    static public void reverseString(char[] s) {
        if (s == null) {
            return;
        } else if (s.length == 1) {
            return;
        }

        int l = 0, r = s.length - 1;

        while (l <= r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }

    }

    //557.反转字符串中的单词
    static public String reverseWords(String s) {
        if (s == null) {
            return null;
        } else if (s.length() == 1) {
            return s;
        }

        String[] array = s.split(" ");
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < array.length; i++) {
            String reverse = reverse(array[i]);

            builder.append(reverse);
            if (i + 1 < array.length) {
                builder.append(" ");
            }

        }

        return builder.toString();

    }

    static public String reverse(String str) {
        if (str == null) {
            return null;
        }
        char[] array = str.toCharArray();
        int l = 0, r = array.length - 1;
        while (l <= r) {
            char temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            l++;
            r--;
        }
        StringBuilder builder = new StringBuilder();
        for (char c : array) {
            builder.append(c);
        }
        return builder.toString();
    }

    //面试题01.07 选择矩阵
    static public int[][] rotate(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;


        int[][] template = new int[row][col];
        int count = 0;
        for (int i = 0, k = col - 1; i < matrix.length && k >= 0; i++, k--) {
            for (int j = 0; j < matrix[0].length; j++) {
                template[count++][k] = matrix[i][j];

            }
            count = 0;
        }

        return template;
    }//暴力算法，使用额外空间

    static public void rotate2(int[][] matrix) {
        if (matrix == null) {
            return;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        //先以对角线，交换
        for (int i = 0; i < rows; i++) {
            for (int j = i + 1; j < cols; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }


        //再行的中点进行交换
        int mid = cols >>> 1;

        for (int i = 0; i < rows; i++) {
            for (int j = 0, k = cols - 1; j < mid && k >= mid; j++, k--) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][k];
                matrix[i][k] = temp;
            }

        }


    }


    //面试题01.08 零矩阵
    static public void setZeroes(int[][] matrix) {
        if (matrix == null) {
            return;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;


        HashMap<Integer, int[]> map = new HashMap<>();
        int count = 1;

        //找到所有0元素的下标
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    map.put(count++, new int[]{i, j});
                }
            }

        }

        Set<Integer> keySet = map.keySet();
        for (Integer integer : keySet) {
            int[] arr = map.get(integer);
            //将这个0元素的行列设为0
            for (int i = arr[0]; i <= arr[0]; i++) {
                for (int j = 0; j < cols; j++) {
                    matrix[i][j] = 0;
                }
            }
            for (int j = arr[1]; j <= arr[1]; j++) {
                for (int i = 0; i < rows; i++) {
                    matrix[i][j] = 0;
                }
            }
        }


    }


    //面试题01.09 字符串轮转
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        return (s1 + s1).contains(s2);
    }


    //面试题02.01 移除重复节点
    public static ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode temp = head;
        HashSet<Integer> hashSet = new HashSet<>();
        hashSet.add(temp.val);
        while (true) {
            if (temp.next == null) {
                break;
            }

            if (!hashSet.add(temp.next.val)) {
                temp.next = temp.next.next;
                if (temp.next == null) {
                    break;
                }
                continue;


            } else {
                hashSet.add(temp.next.val);
            }


            temp = temp.next;

        }

        return head;

    }


    //遍历单链表
    static public void list(ListNode head) {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            System.out.println(head);
        }

        ListNode temp = head;
        while (true) {
            if (temp.next == null) {
                System.out.println(temp);
                break;
            }
            System.out.println(temp);
            temp = temp.next;

        }

    }


    //面试题02.02 返回倒数第k个节点
    static public int kthToLast(ListNode head, int k) {
        if (head == null) {
            return -1;
        }
        ListNode temp = head;

        //先获取链表长度
        int len = 1;

        while (true) {

            if (temp.next == null) {
                break;
            } else {
                len++;
            }
            temp = temp.next;

        }
        temp = head;

        if (k < 0 || k > len) {
            return -1;
        }

        int count = len - k;


        for (int i = 0; i < count; i++) {
            temp = temp.next;
        }

        return temp.val;
    }

    //面试题02.03 删除中间节点
    public void deleteNode(ListNode node) {
        if (node == null) {
            return;
        }

        node.val = node.next.val;
        node.next = node.next.next;

    }

    //面试题02.04 分隔链表
    static public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        if (head.next == null) return head;


        ListNode temp = head;
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode sTemp = small;
        ListNode bTemp = big;


        while (true) {

            if (temp == null) {
                break;
            }

            if (temp.val < x) {

                sTemp.next = temp;
                sTemp = sTemp.next;
            } else {
                bTemp.next = temp;
                bTemp = bTemp.next;
            }

            temp = temp.next;

        }
        bTemp.next = null;

        sTemp.next = big.next;

        return small.next;
    }


    public static void main(String[] args) {


       /* int[][] arr = new int[3][3];

        arr[0][0] = 1;
        arr[0][1] = 1;
        arr[0][2] = 1;
        arr[1][0] = 1;
        arr[1][1] = 0;
        arr[1][2] = 1;
        arr[2][0] = 1;
        arr[2][1] = 1;
        arr[2][2] = 1;*/

        ListNode head = new ListNode(1);

        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(2);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node = partition(head, 3);


        list(node);

    }

}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    ListNode(int x) {
        val = x;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}
